package l.l.w.CodingInterviews;

import java.util.ArrayList;

/**
 * Created by llw on 2018/4/7/0007.
 */
public class 和为S的连续正数序列 {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        int an = 0,a1 = 0;
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int stop = (int)Math.sqrt(2 * sum);
        int n = stop;
        while(n >= 2){
            int mid = sum / n;
            /*if((n % 2) == 0){//偶数
                a1 = mid - (n >> 1) + 1;
                an = mid + (n >> 1);
            }else{
                a1 = mid - (n >> 1);
                an = mid + (n >> 1);
            }*/
            a1 = mid - ((n - 1) >> 1);
            an = mid + (n >> 1);
            if(a1 <= 0 || an >= sum) break;
            int curSum = ((a1 + an) * n) >> 1;
            if(curSum == sum){
                ArrayList<Integer> oneAnswer = new ArrayList<Integer>(n);
                for(int i = a1; i <= an; ++i){
                    oneAnswer.add(i);
                }
                result.add(oneAnswer);
            }
            --n;
        }
        return result;
    }

    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> result = new 和为S的连续正数序列().FindContinuousSequence(9);
        System.out.println(result);
    }
}
